package stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class t20 {

    public static void main(String[] args) {
        t20 t20 = new t20();
        System.out.println(t20.isValid("()"));
    }

    public boolean isValid(String s) {
        //很经典的栈，先进后出
        Stack stack = new Stack();

        Map<String, String> map = new HashMap(3);
        map.put(")", "(");
        map.put("}", "{");
        map.put("]", "[");

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')' ||
                    s.charAt(i) == '}' ||
                    s.charAt(i) == ']') {
                // 需要从栈取
                if (stack.empty()) {
                    return false;
                }
                String p = String.valueOf(stack.pop());

                if (!map.get(String.valueOf(s.charAt(i))).equals(p)) {
                    return false;
                }
            } else {
                stack.push(s.charAt(i));
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    public boolean isValid2(String s) {

        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == ')' && !stack.empty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        if (stack.isEmpty()) {
            return true;
        }

        return false;
    }
}